package zhengqc.sort;

public class HeapSort<E extends Comparable<E>> extends Sort<E> {
    public HeapSort() {
        this.sortName = "HeapSort";
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的父节点的索引 */
    protected int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index: 0 doesn't have parent");
        }
        return (index-1) / 2;
    }
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的左孩子节点的索引 */
    protected int leftChild(int index) {
        return 2 * index + 1;
    }
    /* 返回完全二叉树的数组中, 一个索引所表示的元素的右孩子节点的索引 */
    protected int rightChild(int index) {
        return 2 * index + 2;
    }
    /* 对 data[0, n) 所形成的最大堆中, 索引为 k 的元素执行 siftDown */
    protected void siftDown(E[]data,  int k, int n) {
        // 当没有左孩子（此时也没有右孩子）时, 结束 sift down
        while (leftChild(k) < n) {
            int j = leftChild(k);
            // 当有右孩子且右孩子的值大于左孩子的值, 则指针 j 指向 右孩子
            if ( (j + 1 < n) &&
                    (data[j+1].compareTo(data[j]) > 0) ) {
                ++ j; // data[j] 是 data[leftChild] 和 data[rightChild] 中的最大值
            }
            // 如果 data[index] 的值不小于 data[j]（即同时不小于左右孩子节点的值）, 则停止 sift down
            if ( data[k].compareTo(data[j]) >= 0 ) {
                break;
            }
            swap(data, k, j);
            k = j;
        }
    }
    @Override
    public void sort(E[] array) {
        if (array.length <= 1) return;
        int n = array.length;
        // heapify
        for (int i = this.parent(n-1); i >= 0; --i) {
            siftDown(array, i, n);
        }
        for (int i = array.length-1; i >= 0; --i) {
            swap(array, 0, i);
            siftDown(array, 0, i);
        }
    }

}
